1. Field of Invention
This invention generally relates to processing compressed digital images. More particularly, this invention relates to methods and apparatus which accomplish rotation in conjunction with variable-length compression/decompression operations.
2. Description of Related Art
Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links to reduce the transmission time or required bandwidth. Similarly, compression is preferred in image storage systems, including digital printers and copiers, where xe2x80x9cpagesxe2x80x9d of a document to be printed are stored temporarily in precollation memory. The amount of media space on which the image data is stored can be substantially reduced with compression. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are often large, and thus make desirable candidates for compression.
The image compression standard disseminated by the Joint Photographic Experts Group (JPEG) committee is a compression technique which reduces data redundancies based on pixel-to-pixel correlations. Generally, a photographic image does not change very much on a pixel-to-pixel basis and therefore has what is known as xe2x80x9cnatural spatial correlation.xe2x80x9d In natural scenes, correlation is generalized, but not exact. Noise makes each pixel somewhat different from its neighbors.
The methods and apparatus of this invention seek to enhance the conventional methods for rotating digital images. In a conventional method for rotating digital images, an image source provides the compressed image data to the system. The image source can be an input device such as a camera or scanner, a transmission channel or a storage device. The compressed image data is input to a decompression unit that reconstructs the image. The uncompressed image is fed into the image rotation unit. The image output is sent to an output image sink, which can be a storage device, a transmission line, or a display device such as a printer or monitor. The disadvantage of this conventional method is that the rotation operations are performed on the decompressed image. Color documents typically contain tens of millions of pixels, such that even simple operations on those image can be computationally and economically expensive and time consuming.
This invention provides a method and apparatus for rotating a compressed digital image as it is decompressed.
This invention separately provides a method and apparatus that generates additional information as the digital image is compressed, where the additional information is used during decompression to rotate the digital image.
This invention separately provides a method and apparatus that generates, as additional information, the DC values of each scanline and pointers to the start position of each initial block of the current scanline.
This invention separately provides a method and apparatus that generate additional information to rotate a digital image that can be stored using a small amount of memory space.
The methods and apparatus of this invention provide an improved image rotation process by reducing its complexity. The methods and apparatus of this invention reduce the computational effort spent in decompressing and rotating a decompressed image. In the methods and apparatus of this invention, rotation is assumed to be an operation which rotates the image by +90xc2x0 or xe2x88x9290xc2x0 or may even represent image transposition. The rotation operations can also be combined with image mirroring in the vertical or horizontal direction.
The methods and apparatus of this invention expand on a variable-length compression operation by adding an image rotation operation, where the Mxc3x97M blocks within the image are orthogonally rotated to rotate the entire image using the compressed image blocks, to avoid the need for buffering the entire image or large sections of it.
More particularly, the methods and apparatus of this invention reduce the memory necessary to orthogonally rotate a digital image in conjunction with a variable-length compression technique, such as Huffman encoding A small amount of auxiliary information, including pointers to the start of the scanlines and the DC coefficients, are stored. A significantly reduced, small-sized block of working memory can be used to save this information. In particular, the space required to store this additional information is proportional to the square root of the space required by the compressed image.
One aspect of this invention deals with a basic problem in digital image processing systems regarding the memory-intensive and computationally-intensive image rotation operation. This aspect is further based on the discovery of a technique that alleviates this problem. This technique associates the rotation of a small image segment or block with decompressing that small image segment or block, and managing the rotated-decompressed blocks to enable rotation using minimal buffer memory.
By avoiding the very expensive process of rotating the decompressed image, the method and apparatus of this invention reduces the computation necessary to rotate a digital image. Using the method and apparatus of this invention, the rotated image has excellent quality without requiring a full buffer""s worth of memory.
The method and apparatus of this invention can be implemented, for example, by modifying basic JPEG compression and decompression methods, where image rotation is performed on the compressed image data (compressed units). Accordingly, the method and apparatus of this invention can be applied to any number of devices, including digital printers and copiers, that need to provide a rotated image. The apparatus according to this invention includes data or image processing systems capable of compressing images.
These and other features and advantages of this invention are described in or are apparent from the following detailed description of the preferred embodiments.